/**
 * @author Daniel Bergqvist 900203-2432
 * @author Marika Hansson 910305-0804
 */
import testSortCol.CollectionWithGet;
import datastructures.BinarySearchTree;

public class SplayTree<E extends Comparable<? super E>> extends
		BinarySearchTree<E> implements CollectionWithGet<E> {

	/**
	 * Method to find an element in the three
	 * 
	 * @param current
	 *            node we are on
	 * @param element
	 *            that we want to find in the three
	 * @return entry with the element we wanted to find, the parent to were the
	 *         element should have been if it doesn't exist in the tree and null
	 *         if the three is empty
	 */
	protected E find(Entry current, E element) {
		if (current == null) {
			return null;
		} else {
			int value = element.compareTo(current.element);
			if (value < 0) {
				if (current.left == null) {
					splay(current);
					return null;
				} else {
					return find(current.left, element);
				}
			} else if (value > 0) {
				if (current.right == null) {
					splay(current);
					return null;
				} else {
					return find(current.right, element);
				}
			} else {
				splay(current);
				return root.element;
			}
		}
	}

	/**
	 * A method used for counting what splay operation is to be used when
	 * splaying up an Entry x.
	 * 
	 * @param x
	 *            Entry to splay on
	 * @return true if the splay was successful and false if it wasn't
	 */
	private void splay(Entry x) {
		if (x != null) {
			if (x.parent == null) {
				root = x;
			} else {
				if (x.parent.parent == null) {
					if (x.parent.left == x) {
						zag(x.parent);
					} else {
						zig(x.parent);
					}
					root = x.parent;
				} else {
					if (x.parent.parent.left != null
							&& x.parent.parent.left.left == x) {
						zagZag(x.parent.parent);
						splay(x.parent.parent);
					} else if (x.parent.parent.right != null
							&& x.parent.parent.right.right == x) {
						zigZig(x.parent.parent);
						splay(x.parent.parent);
					} else if (x.parent.parent.left != null
							&& x.parent.parent.left.right == x) {
						zagZig(x.parent.parent);
						splay(x.parent);
					} else {
						zigZag(x.parent.parent);
						splay(x.parent);
					}
				}
			}
		}
	}

	/*
	 * splays up the left child from the given entry
	 */
	private void zag(Entry x) {
		Entry y = x.left;
		E temp = x.element;
		x.element = y.element;
		y.element = temp;
		x.left = y.left;
		if (x.left != null)
			x.left.parent = x;
		y.left = y.right;
		y.right = x.right;
		if (y.right != null)
			y.right.parent = y;
		x.right = y;
	}

	/*
	 * splays up the right child from the given entry
	 */
	private void zig(Entry x) {
		Entry y = x.right;
		E temp = x.element;
		x.element = y.element;
		y.element = temp;
		x.right = y.right;
		if (x.right != null)
			x.right.parent = x;
		y.right = y.left;
		y.left = x.left;
		if (y.left != null)
			y.left.parent = y;
		x.left = y;
	}

	/*
	 * Splays up the left-right grandchild of a given entry.
	 */
	private void zagZig(Entry x) {
		Entry y = x.left, z = x.left.right;
		E e = x.element;
		x.element = z.element;
		z.element = e;
		y.right = z.left;
		if (y.right != null)
			y.right.parent = y;
		z.left = z.right;
		z.right = x.right;
		if (z.right != null)
			z.right.parent = z;
		x.right = z;
		z.parent = x;
	}

	/*
	 * Splays up the right-left grandchild of a given entry.
	 */
	private void zigZag(Entry x) {
		Entry y = x.right, z = x.right.left;
		E e = x.element;
		x.element = z.element;
		z.element = e;
		y.left = z.right;
		if (y.left != null)
			y.left.parent = y;
		z.right = z.left;
		z.left = x.left;
		if (z.left != null)
			z.left.parent = z;
		x.left = z;
		z.parent = x;
	}

	/*
	 * Splays up the right-right grandchild of a given entry.
	 */
	private void zigZig(Entry x) {
		Entry y = x.right, z = x.right.right;
		E e = x.element;
		x.element = z.element;
		z.element = e;
		y.right = z.left;
		if (y.right != null) {
			y.right.parent = y;
		}
		z.left = x.left;
		if (z.left != null) {
			z.left.parent = z;
		}
		x.left = y;
		x.right = z.right;
		if (x.right != null) {
			x.right.parent = x;
		}
		z.right = y.left;
		if (z.right != null) {
			z.right.parent = z;
		}
		y.left = z;
	}

	/*
	 * Splays up the left-left grandchild of a given entry
	 */
	private void zagZag(Entry x) {
		Entry y = x.left, z = x.left.left;
		E e = x.element;
		x.element = z.element;
		z.element = e;
		y.left = z.right;
		if (y.left != null) {
			y.left.parent = y;
		}
		z.right = x.right;
		if (z.right != null) {
			z.right.parent = z;
		}
		x.right = y;
		x.left = z.left;
		if (x.left != null) {
			x.left.parent = x;
		}
		z.left = y.right;
		if (z.left != null) {
			z.left.parent = z;
		}
		y.right = z;
	}

	/*
	 * Given an Entry e it calls the fins method to see if the entry is in the
	 * three and then calls a method for splaying it (or it's parent if not
	 * found) to the root.
	 * 
	 * @return the entry that we search for in the three if it exists or null if
	 * it doesn't
	 */
	@Override
	public E get(E e) {
		if (root == null) {
			return null;
		}
		return find(root, e);
	}
}